package com.yusong.algorithm.array;

import java.util.Arrays;

/**
 * 三路快排
 * Partition
 */
public class Index3Sort {

    public static void main(String[] args) {
        int[] grid = {2,0,2,1,1,0};

        Index3Sort main = new Index3Sort();

        main.sortColors(grid);

        System.out.println(Arrays.toString(grid));
    }

    public void sortColors(int[] nums) {
        int length = nums.length;
        //0的右开合边界
        int startIndex = 0;
        //2的左闭合边界
        int endIndex = length;
        int middle = 0;
        while(middle<endIndex){
            int currentValue = nums[middle];
            if(currentValue == 1){
                middle++;
            }else if(currentValue == 2){
                endIndex--;
                switchNum(nums, middle, endIndex);
            }else if(currentValue == 0){
                //同向指针特殊处理
                //慢指针移动，同向快指针也需要移动
                switchNum(nums, middle, startIndex);
                startIndex++;
                middle++;
            }
            System.out.println(startIndex+"|"+middle+"|"+ endIndex+"---"+ currentValue +" ="+ Arrays.toString(nums));
        }
    }

    private void switchNum(int[] nums,int m, int n){
        int temple = nums[m];
        nums[m] = nums[n];
        nums[n] = temple;
    }
}
